翻訳と辞書 Words near each other ・ "O" Is for Outlaw ・ "O"-Jung.Ban.Hap. ・ "Ode-to-Napoleon" hexachord ・ "Oh Yeah!" Live ・ "Our Contemporary" regional art exhibition (Leningrad, 1975) ・ "P" Is for Peril ・ "Pimpernel" Smith ・ "Polish death camp" controversy ・ "Pro knigi" ("About books") ・ "Prosopa" Greek Television Awards ・ "Pussy Cats" Starring the Walkmen ・ "Q" Is for Quarry ・ "R" Is for Ricochet ・ "R" The King (2016 film) ・ "Rags" Ragland ・ ! (album) ・ ! (disambiguation) ・ !! ・ !!! ・ !!! (album) ・ !!Destroy-Oh-Boy!! ・ !Action Pact! ・ !Arriba! La Pachanga ・ !Hero ・ !Hero (album) ・ !Kung language ・ !Oka Tokat ・ !PAUS3 ・ !T.O.O.H.! ・ !Women Art Revolution Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク trace monoid ： ウィキペディア英語版 trace monoid In computer science, a trace is a set of strings, wherein certain letters in the string are allowed to commute, but others are not. It generalizes the concept of a string, by not forcing the letters to always be in a fixed order, but allowing certain reshufflings to take place. Traces were introduced by Cartier and Foata in 1969 to give a combinatorial proof of MacMahon's Master theorem. Traces are used in theories of concurrent computation, where commuting letters stand for portions of a job that can execute independently of one another, while non-commuting letters stand for locks, synchronization points or thread joins.〔Sándor & Crstici (2004) p.161〕 The trace monoid or free partially commutative monoid is a monoid of traces. In a nutshell, it is constructed as follows: sets of commuting letters are given by an independency relation. These induce an equivalence relation of equivalent strings; the elements of the equivalence classes are the traces. The equivalence relation then partitions up the free monoid (the set of all strings of finite length) into a set of equivalence classes; the result is still a monoid; it is a quotient monoid and is called the ''trace monoid''. The trace monoid is universal, in that all homomorphic monoids are in fact isomorphic. Trace monoids are commonly used to model concurrent computation, forming the foundation for process calculi. They are the object of study in trace theory. The utility of trace monoids comes from the fact that they are isomorphic to the monoid of dependency graphs; thus allowing algebraic techniques to be applied to graphs, and vice versa. They are also isomorphic to history monoids, which model the history of computation of individual processes in the context of all scheduled processes on one or more computers. ==Trace== Let $\backslash Sigma^$ * denote the free monoid, that is, the set of all strings written in the alphabet $\backslash Sigma$. Here, the asterisk denotes, as usual, the Kleene star. An independency relation $I$ on $\backslash Sigma$ then induces a binary relation $\backslash sim$ on $\backslash Sigma^$ *, where $u\backslash sim\; v\backslash ,$ if and only if there exist $x,y\backslash in\; \backslash Sigma^$ *, and a pair $(a,b)\backslash in\; I$ such that $u=xaby$ and $v=xbay$. Here, $u,v,x$ and $y$ are understood to be strings (elements of $\backslash Sigma^$ *), while $a$ and $b$ are letters (elements of $\backslash Sigma$). The trace is defined as the symmetric, reflexive and transitive closure of $\backslash sim$. The trace is thus an equivalence relation on $\backslash Sigma^$ *, and is denoted by $\backslash equiv\_D$. The subscript ''D'' on the equivalence simply denotes that the equivalence is obtained from the independency ''I'' induced by the dependency ''D''. Clearly, different dependencies will give different equivalence relations. The transitive closure simply implies that $u\backslash equiv\; v$ if and only if there exists a sequence of strings $(w\_0,w\_1,\backslash cdots,w\_n)$ such that $u\backslash sim\; w\_0\backslash ,$ and $v\backslash sim\; w\_n\backslash ,$ and $w\_i\backslash sim\; w\_\backslash ,$ for all . The trace monoid, commonly denoted as $\backslash mathbb\; (D)$, is defined as the quotient monoid :$\backslash mathbb\; (D)\; =\; \backslash Sigma^$ * / \equiv_D. The homomorphism :$\backslash phi\_D:\backslash Sigma^$ *\to \mathbb (D) is commonly referred to as the natural homomorphism or canonical homomorphism. That the terms ''natural'' or ''canonical'' are deserved follows from the fact that this morphism embodies a universal property, as discussed in a later section. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「trace monoid」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.